import java.util.HashMap;

/**
* @description: 149. 直线上最多的点数
* @author hewei
* @date 2022/7/27 16:14
* @version 1.0
*/

public class MaxPoints {

    public static void main(String[] args) {
        int[][] points = {{2,3},{3,3},{-5,3}};
        System.out.println(new MaxPoints().maxPoints(points));
    }

    public int maxPoints1(int[][] points) {
        int ans = 0;
        for (int i = 0; i < points.length - 1; i++) {
            HashMap<Double, Integer> map = new HashMap<>();
            for (int j = i + 1; j < points.length; j++) {
                double temp;
                if (points[j][0] - points[i][0] == 0) {
                    temp = Integer.MAX_VALUE;
                } else {
                    temp = (double) (points[j][1] - points[i][1]) / (points[j][0] - points[i][0]);
                    if (temp == -0.0) temp = 0.0;
                }
                map.put(temp, map.getOrDefault(temp, 0) + 1);
                ans = Math.max(map.get(temp), ans);
            }
        }
        return ans + 1;
    }

    public int maxPoints(int[][] points) {
        int ans = 0;
        for (int i = 0; i < points.length - 1; i++) {
            if (ans >= points.length - i - 1) break;
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int j = i + 1; j < points.length; j++) {
                int x = points[j][0] - points[i][0];
                int y = points[j][1] - points[i][1];
                if (x == 0) {
                    y = 1;
                } else if (y == 0) {
                    x = 1;
                } else {
                    if (y < 0) {
                        x = -x;
                        y = -y;
                    }
                    int gcd = gcd(Math.abs(x), Math.abs(y));
                    x /= gcd;
                    y /= gcd;
                }
                int temp = x + y * 20001;
                map.put(temp, map.getOrDefault(temp, 0) + 1);
                ans = Math.max(ans, map.get(temp));
            }
        }
        return ans + 1;
    }

    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
